package primary.primary0;

/**
 * log(m+n) 肯定只能二分查找
 * 寻找第k小的数，因为是有序的，所以我们可以一半一半截，每次截取一部分(见官方方案3，其他的不要看)
 *
 */
public class S0004寻找两个正序数组的中位数 {
    // 100, 非二分查找, 但是我只能这样了。
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null){
            return -1;
        }
        int length1 = nums1.length;
        int length2 = nums2.length;
        if(((length1 + length2) & 1) == 1){
            return findMedian1(nums1, nums2, (length1 + length2) >> 1);
        }else{
            return findMedian2(nums1, nums2, (length1 + length2) >> 1);
        }

    }
    // 总长度为奇数, 寻找一个中位数
    private double findMedian1(int[] nums1, int[] nums2, int aimLoc){
        return findAimLoc1(nums1, nums2, aimLoc + 1);

    }

    // 总长度为偶数, 寻找两个中位数的均值
    private double findMedian2(int[] nums1, int[] nums2, int aimLoc){
        return (double)(findAimLoc1(nums1, nums2, aimLoc) + findAimLoc1(nums1, nums2, aimLoc + 1)) / 2;
    }

    // 寻找指定位置的数
    private int findAimLoc1(int[] nums1, int[] nums2, int aimLoc){
        int count1 = 0;
        int count2 = 0;
        // int targetValue = nums1[0] < nums2[0]? nums1[0]: nums2[0];
        int targetValue = -2233;
        while(aimLoc != 0){
            if(count1 == nums1.length){
                return nums2[count2 + aimLoc - 1];
            }
            if(count2 == nums2.length){
                return nums1[count1 + aimLoc - 1];
            }
            if(nums1[count1] < nums2[count2]){
                targetValue = nums1[count1];
                count1 ++;
            }else{
                targetValue = nums2[count2];
                count2 ++;
            }
            aimLoc --;
        }
        return targetValue;
    }
}
